Exercise: Random Binary Search Trees
Implement a treap from a sorted array.
We'll cover the following
Task#
Design and implement an algorithm that constructs a Treap from a sorted array, a, of n elements. This method should run in worst-case time and should construct a Treap that is indistinguishable from one in which the elements of a were added one at a time using the add(x) method.
Sample input
The sample input will be as follows:
1
2
3
4
5
6
Expected output
The expected output will be as follows:
Tree contents:
1 2 3 4 5 6
Tree contents after removing 4:
1 2 3 5 6
Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.
Good luck!
Note: You must implement the method
addall()andaddallrecursive()in the below code starting at line 19.
Discussion on Random Binary Search Trees
Solution: Random Binary Search Trees